Buffered multistage interconnection networks are often used in Asynchronous Transfer Mode (“ATM”) and other types of packet switching systems. Networks of this type use buffers to store packets at intermediate points when contention for output links prevents immediate transmission. As used herein, the term packet is used to indicate generically addressable data packets of all types, including fixed length cells and variable length packets.
Many multistage interconnection networks provide multiple paths between network inputs and outputs, allowing the traffic to be balanced across the alternative paths. An example of such a network is shown in FIG. 1A, which is a depiction of an architecture known as a three stage Bene{hacek over (s)} network. The Bene{hacek over (s)} network 10 is composed of three stages of switch elements (SE) 12, 14, 16 and two webs of interconnecting links (IL) 18, 20. Switch elements 12, 14, 16 may have any number of input type interconnecting links 24 and output type interconnecting links 26. Letting d denote the number of input links and the number of output links in a single switch element and letting n denote the number of input links and output links of the multistage network as a whole, FIG. 1A illustrates d=4 and n=16. Traffic distribution in a multistage network 10 is commonly done in one of two ways for a given end-to-end session of sending packets from an identified input to an identified output of the network. In systems that use static routing, all packets associated with a given session follow the same path through the interconnection network. (In ATM networks, a session is typically associated with a virtual circuit.) This path is selected when the session begins and typically remains fixed until the session is completed, thus guaranteeing that packets belonging to the same session are forwarded in the order they arrived.
In systems that use dynamic routing, traffic is distributed on a packet-by-packet basis so as to equalize the traffic load across the entire interconnection network. Dynamic routing systems can distribute traffic more evenly than systems that use static routing. Consequently, dynamic routing systems can be operated with lower speed internal links than are needed for systems that use static routing. However, because dynamic routing systems do not constrain the packets belonging to a single user session to a single path, they may allow packets in a given session to get out of order, that is, lose sequence.
Systems using dynamic routing typically provide resequencing mechanisms to restore the correct packet order at the outputs of the switching system. Conventional mechanisms for resequencing usually ensure that packets are delivered in the correct order, but under unusual conditions, they can fail to reorder packets correctly.
A known method for resequencing ATM packets in a multistage interconnection network uses timestamps and time-ordered output queues. Such systems require a central timing reference. The central timing reference signal is distributed to the circuits at all inputs to the network and to the circuits at all outputs. When a packet of data enters the network at an input, the current time is inserted into a timestamp field in the packet. When the packet emerges from the network at the appropriate destination, the timestamp is used to insert the packet into a time-ordered queue. In other words, the packets are read from the queue in increasing order of their timestamp values. Associated with the queue is an age threshold or timeout which specifies the minimum time that must elapse between the time a packet entered the interconnection network and the time it is allowed to leave the resequencing buffer at the output. If the difference between the current time and the timestamp of the first packet in the buffer is smaller than the age threshold, then the first packet is held back (along with all others “behind” it in the buffer). This allows packets that are delayed for a long period of time in the interconnection network to catch up with other packets that experience smaller delays.
If the age threshold is larger than the maximum delay that packets ever experience in the interconnection network, then the time-based resequencing method will always deliver packets in order. However, if packets are delayed by more than the time specified by the age threshold or timeout, errors may occur. In typical systems, delays in the interconnection network are usually fairly small (a few packet times per stage) and packets only rarely experience long delays. On the other hand, a worst-case delay may be very large. As a result, the age threshold is usually set not to the worst-case delay, but to a smaller value chosen to give an acceptably small frequency of resequencing errors. The resequencing delay can be traded off against reduced probability of resequencing errors. Conventional time-based resequencing methods can be implemented in various ways.
Merge sorting, illustrated in FIG. 1B, is a known technique for producing a single sorted list from multiple ordered lists whose values are known a priori. For example, two lists 920 and 922 of known elements sorted in ascending order can be combined into a single sorted list 924 by repeatedly taking the smaller value from the front of lists 920 and 922, and appending the smaller value to the end of list 924. This example can be extended to a set of n known values, which can be sorted by first dividing the set into n lists containing a single value each, then combining pairs of lists to produce n/2 lists with two values each. Pairs of these lists are then merged, producing n/4 list with four values each. Continuing in this fashion eventually yields a single sorted list containing the original values, but in sorted order, as shown in FIG. 1B. Merge sorting an also be implemented using three-way merging (that is, merging three sorted list into a single sorted list in one step), rather than by using two-way merging. More genely, d-way merging can be used for any integer d>1.
However, known sorting techniques are not candidates for resequencing packets in a packet switching environment. In such a dynamic environment, lists of known values are not available. Rather, these packet switching systems must resequence streams of packets. Moreover, in dynamic resequencing systems, a complete set of packets to be resequenced is routinely not available at the time resequencing decisions must be made. Furthermore, the resequencing process is additionally complicated because the streams of packets to be resequenced can be temporarily empty.
Needed are new methods, apparatus, and systems for resequencing information in a dynamic environment.
Prior work known to the inventors is reflected in the following references:
T. J. Chaney, A. Fingerhut, M. Flucke, J. Turner, “Design of a Gigabit ATM Switch,” Proceedings of Infocom, April 1997.
Z. Dittia, A. Fingerhut, J. Turner, “System Architecture Document for Gigabit Switching Technology,” Version 3.10, Washington University Applied Switching Laboratory, January 1996.
J. S. Turner, “An Optimal Nonblocking Multicast Virtual Circuit Switch,” Proceedings of Infocom, June 1994.
M. A. R. Henrion, U.S. Pat. No. 5,127,000, issued Jun. 30, 1992, entitled Resequencing System for a Switching Node.
J. S. Turner, U.S. Pat. No. 5,260,935, issued Nov. 9, 1993 for Data Packet Resequencer.
J. S. Turner, U. S. Pat. No. 5,339,311, issued Aug. 16, 1994, for Data Packet Resequencer.
J. S. Turner, U.S. Pat. No. 5,402,415, issued Mar. 28, 1995, Multicast Virtual Circuit Switch Using Cell Recycling.